package 牛客_面试必刷.Month07.day12;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class 数组中只出现一次的两个数字 {
    public int[] FindNumsAppearOnce (int[] array) {
        int res = 0;
        //首先一直异或，异或到最后的数字肯定是 a ^ b得到的
        //异或规则：两数相等为0，不等为1
        for(int i:array){
            res ^= i;
        }
        //然后通过 &1 来寻找从低到高第一个a 和 b不同的二进制位，因为只有 1 & 1 == 1，其他都不等
        int key = 1;
        while((res & key) == 0){//这里是我的问题，为什么是0呢？不应该是1嘛？（解答这个问题，因为等你到高位的时候对应的数字就不是1了）
            key <<= 1;
        }
        int a = 0;
        int b = 0;
        for (int i = 0; i < array.length; i++) {
            //找到之后进行判断
            if((array[i] & key) == 0){
                a ^= array[i];
            }else{
                b ^= array[i];
            }
        }
        if(a > b){
            int tmp = a;
            a = b;
            b = tmp;
        }
        return new int[]{a,b};
    }
}
